#Definition for singly-linked list.
class ListNode(object):
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        # 创建一个值为 1 的头节点
        head = ListNode(1)
        p=head
        while list1 and list2:
            if list1.val<=list2.val:
                p.next=list1
                list1=list1.next
            else:
                p.next=list2
                list2=list2.next
            p=p.next
        if list1:
            p.next=list1
        if list2:
            p.next=list2
        return head.next



def list_to_linkedlist(lst):
    dummy = ListNode(-1)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 辅助函数：将链表转换为普通列表以便打印
def linkedlist_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# 测试代码
solution = Solution()
list1 = list_to_linkedlist([2, 4, 6])
list2 = list_to_linkedlist([1, 3, 5])
merged_head = solution.mergeTwoLists(list1, list2)
print(linkedlist_to_list(merged_head))